Міністерство освіти і науки, молоді та спорту України
Національний університет “Львівська політехніка”
Кафедра ЕОМ
Звіт
з лабораторної роботи № 4
на тему:
" Структура даних ЧЕРГА "
з дисципліни:
" Програмування. Частина III. Структури даних та алгоритми "
№ варіанта = [(2) + (111)] % 30 + 1=24
1. МЕТА РОБОТИ
Вивчення фундаментальної абстрактної структури даних - черги. Набуття практичних навичок побудови черги, дослідження динаміки її вмісту та використання черг для розв'язання прикладних задач.
ПОСТАНОВКА ЗАДАЧІ
Змоделювати чергу або дек на базі статичного масиву згідно з завданням. Написати основні операції для роботи з чергою (push, pop, front, empty, full) або деком (push_left, push_right, pop_left, pop_right, front_left, front_right, empty, full) і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>10) різних цілих чисел (числа вводити з клавіатури). Всі додатні числа послідовно заносити в чергу (дек), кожне від’ємне число має вилучати з черги (деку) один елемент (при роботі з деком, парні числа працюють з правим кінцем деку, а непарні – з лівим). Виводити на екран динаміку вмісту черги (деку) під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу основних операцій та генерувала виникнення ситуацій "втрати значимості черги"(queue underflow) і "переповнення черги" (queue overflow) або "втрати значимості деку"(deq underflow) і "переповнення деку" (deq overflow).
Примітка: після реалізації черги або деку працювати з ними як з абстрактними типами даних, а не як з масивами.
24. Змоделювати дек (тобто додавати i вилучати елементи можна з обох кінців). Після обробки всієї заданої вхідної послідовності перевірити, чи є у деку три однакових числа, які йдуть підряд одне за одним.
3. Динаміка вмісту черги (або деку)
3.1. Задаємо вхідну послідовність 10 цілих чисел: 2, -4, -3, 3, 4, 7, -8, 8, 6, 6.
3.2. Схематичне зображення деку після обробки кожного числа з вхідної послідовності
Порожній дек
push_right (2);
pop_right( );
pop_left( );
Втрата значимості деку!
push_left (3);
push_right (4);
push_left (7);
pop_right ( );
push_right (8);
push_right (6);
push_right (6);
Переповнення деку!
3.3. Перевірка умови
Чи є у деку три однакових числа, які йдуть підряд одне за одним?
Умова не виконується!
4. Алгоритм розв’язання задачі
ШАБЛОННИЙ ПАРАМЕТР, ОПЕРАТОРИ ПЕРЕІМЕНОВАННЯ ТИПІВ ТА КОНСТАНТНІ ЧЛЕНИ класу Queue<T>
Шаблонний параметр T предтставляє собою тип елементів, що зберігаються у стеку.
Він може бути довільним вбудованим типом в мові С++ а також структурою, класом (в якому визначений конструктор по замовчуванню),конструктор копіювання і оператор присвоєння.
Queue<T>:: CAPACITY предтаставляє максимальну кількість елементів довільної черги (як тільки ця кількість буде досягнута, додавання елементів у чергу припиняється).
КОНСТРУКТОР ШАБЛОННОГО КЛАСУ Queue <Т>
Queue ()
Післяумова: черга ініціалізується порожньою
МОДИФІКУЮЧІ ФУНКЦІЇ-ЧЛЕНИ шаблонного класу Queue <Item>:
bool push_left(const T & k);
Передумова: дек не є повним.
Післяумова: в дек занесена нова копія елемента.
bool pop_left();
Передумова: дек не є порожнім.
Післяумова: вилучається елемент з лівого кінця.
КОНСТАНТНІ ФУНКЦІЇ-ЧЛЕНИ шаблонного класу Queue <T>:
T front_left()const;
Передумова: дек не є порожнім.
Післяумова: повертається елемент лівого кінця, однак дек при цьому не змінюється.
bool empty() const;
Післяумова: повертає значення true, якщо дек порожній, і значення false, якщо це не так.
5. Результати виконання програми
/
Висновки.
На цій лабораторній роботі я вивчив фундаментальну абстрактну структуру даних чергу, набув практичних навичок побудови черги, дослідив динаміку його вмісту та використання черг для розв'язання прикладних задач.
